package Arrays;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class _219_ContainsDuplicateII {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int[] copyNum = new int[nums.length];
        copyNum = Arrays.copyOf(nums,nums.length);
        Arrays.sort(copyNum);
        Map<Integer,Integer> numMap = new HashMap<Integer,Integer>();
        for(int i=0;i<copyNum.length-1;i++) {
            if (copyNum[i] == copyNum[i + 1]) {
                if (numMap.containsKey(copyNum[i])) {
                    numMap.put(copyNum[i], numMap.get(copyNum[i]) + 1);
                } else {
                    numMap.put(copyNum[i],2);
                }
            }
        }
        for (Map.Entry<Integer, Integer> map : numMap.entrySet()) {
            int total = map.getValue();
            int key = map.getKey();
            int count = 0;
            int pos = Integer.MIN_VALUE;
            for(int i=0;i<nums.length;i++) {
                if (nums[i] == key) {
                    count++;
                    if (pos != Integer.MIN_VALUE) {
                        if (i - pos <= k) {
                            return true;
                        } else {
                            pos = i;
                        }
                    }else{
                        pos = i;
                    }
                    if (count == total) {
                        break;
                    }
                }
            }
        }
        return false;
    }
}
